package com.df.sort;

/**
 * @author dongfang
 */
public class Heap {

    /**
     * <EM>堆排序（Heapsort）</EM>是指利用堆这种数据结构所设计的一种排序算法。<br/>
     * 堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：<I>即子结点的键值或索引总是小于（或者大于）它的父节点。<I/>
     * <pre>
     *  不稳定的排序方法
     *  辅助空间为O(1)， 最坏时间复杂度为O(nlog2n)
     *  堆排序的堆序的平均性能较接近于最坏性能。
     * </pre>
     *
     * @param array
     */
    public static void heap(int[] array) {
        int num = 0; // 数据交换次数

        int length = array.length;
        for (int i = (length - 1) >> 1; i > -1; i--) { // 从最后一个父节点开始建堆
            num += heapify(array, i, length);
        }

        int temp;
        for (int i = length - 1; i > 0; i--) {
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            num++;
            // System.out.println("[" + num++ + "][" + i + "][0]\t: " + Arrays.toString(array));
            num += heapify(array, 0, i);
        }
        System.out.println("heap num [" + num + "]");
    }

    /**
     * 建堆--> 大堆
     * <pre>
     * 1. 若array[0，...，n-1]表示一颗完全二叉树的顺序存储模式，则双亲节点指针和孩子结点指针之间的内在关系如下：
     *   任意一节点指针 i：父节点：i==0 ? null : (i-1)/2
     *                   左孩子：2*i + 1
     *                   右孩子：2*i + 2
     * 2. 堆的定义：n个关键字序列array[0，...，n-1]，当且仅当满足下列要求：(0 <= i <= (n-1)/2)
     *            ① array[i] <= array[2*i + 1] 且 array[i] <= array[2*i + 2]； 称为小根堆；
     *            ② array[i] >= array[2*i + 1] 且 array[i] >= array[2*i + 2]； 称为大根堆；
     * </pre>
     *
     * @param array  待建堆数组
     * @param i      父节点下标
     * @param length 数组长度
     * @return num数据交换次数
     */
    private static int heapify(int[] array, int i, int length) {
        int temp = array[i];
        int num = 1;

        for (int j = 2 * i + 1; j < length; j = 2 * j + 1) {  //j为初始化为父节点的左孩子，沿节点较大的子节点向下调整
            if (j < (length - 1) && array[j] < array[j + 1]) {//取节点较大的子节点的下标
                ++j;//如果节点的右孩子>左孩子，则取右孩子节点的下标
            }

            if (temp > array[j]) {
                break;
            }

            //根节点 <左右子女中关键字较大者
            array[i] = array[j]; //将左右子结点中较小值array[j]调整到双亲节点上
            num++;

            //System.out.println("[" + num++ + "][" + i + "][" + j + "]\t: " + Arrays.toString(array));
            i = j;//【关键】修改i值，以便继续向下调整
            array[i] = temp;//被调整的结点的值放人最终位置
        }
        return num;
        // System.out.println("[" + num++ + "][" + i + "][-]\t: " + Arrays.toString(array));
    }

}
